package tree.morris;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Morris {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);
        preorderTraversal(root);
    }

    public void morris(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode mostRight = root.left;
            //如果左子树存在
            if (mostRight != null) {
                //找到左子树的最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                //如果最右节点的右孩子指向null，就让它指向cur，cur往左走，开始下一次循环
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    //如果最右节点的右孩子指向cur，就让它指向null
                    mostRight.right = null;
                }
            }
            //左子树不存在，往右走
            cur = cur.right;
        }
    }

    //使用莫里斯遍历实现先序遍历，如果节点会走两遍，就打印第一次遇到的，如果走一遍，就直接打印
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode mostRight = cur.left;
            //如果左子树存在
            if (mostRight != null) {
                //找到左子树的最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                //如果最右节点的右孩子指向null，就让它指向cur，cur往左走，开始下一次循环
                if (mostRight.right == null) {
                    //这里是走两遍的节点，走的第一遍
                    list.add(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    //如果最右节点的右孩子指向cur，就让它指向null
                    mostRight.right = null;
                    cur = cur.right;
                }
            } else {
                //只走一遍的节点，直接打印
                list.add(cur.val);
                //左子树不存在，往右走
                cur = cur.right;
            }
        }
        return list;
    }
    //中序，走第二遍打印。
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (cur != null) {
            TreeNode mostRight = cur.left;
            //如果左子树存在
            if (mostRight != null) {
                //找到左子树的最右节点
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                //如果最右节点的右孩子指向null，就让它指向cur，cur往左走，开始下一次循环
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    //这里是走两遍的节点，走的第二遍
                    list.add(cur.val);
                    //如果最右节点的右孩子指向cur，就让它指向null
                    mostRight.right = null;
                    cur = cur.right;
                }
            } else {
                //只走一遍的节点，直接打印
                list.add(cur.val);
                //左子树不存在，往右走
                cur = cur.right;
            }
        }
        return list;
    }
}
